package cn.structure.binarytree.bst;

/**
 * 二叉搜索树（BST)实现
 *
 * @author dunlingzi
 */
public class BinarySearchTree<T extends Comparable<T>> {

    /**
     * 根节点
     */
    private BsTreeNode<T> root;

    public BinarySearchTree() {
    }

    public BinarySearchTree(BsTreeNode<T> root) {
        this.root = root;
    }

    public BinarySearchTree(T data) {
        root = new BsTreeNode(data);
    }

    public BsTreeNode<T> getRoot() {
        return root;
    }

    public void setRoot(BsTreeNode<T> root) {
        this.root = root;
    }

    /**
     * 中序排序,递归实现
     */
    public void inOder(BsTreeNode<T> root) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            inOder(root.left);
        }
        System.out.print("->" + root.nodeKey);
        if (root.right != null) {
            inOder(root.right);
        }
    }

    /**
     * 中序排序,递归实现
     */
    public void inOder() {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            inOder(root.left);
        }
        System.out.print("->" + root.nodeKey);
        if (root.right != null) {
            inOder(root.right);
        }
    }

    /**
     * 使用递归实现查找功能
     * 查找包含指定数据的节点
     */
    public BsTreeNode<T> search(BsTreeNode<T> root, T data) {
        if (root == null) {
            return null;
        }

        //将需要查找的值与根节点的值进行比较
        if (data.compareTo(root.nodeKey) > 0) {
            //大于则去右子树查找
            return search(root.right, data);
        } else if (data.compareTo(root.nodeKey) < 0) {
            //小于则去左子树查找
            return search(root.left, data);
        } else {
            //等于
            return root;
        }
    }

    /**
     * 插入节点
     */
    public boolean addTreeNode(BsTreeNode<T> root, BsTreeNode<T> nodeInserted) {
        //根节点为空时,直接将插入节点作为根节点
        if (root.nodeKey == null) {
            root.nodeKey = nodeInserted.nodeKey;
            root.left = nodeInserted.left;
            root.right = nodeInserted.right;
            root.parent = nodeInserted.parent;
            return true;
        }

        //查找合适的位置进行插入
        if (nodeInserted.nodeKey.compareTo(root.nodeKey) > 0) {
            //大于去右子树处理
            if (root.right == null) {
                nodeInserted.parent = root;
                root.right = nodeInserted;
                return true;
            } else {
                return addTreeNode(root.right, nodeInserted);
            }
        } else if (nodeInserted.nodeKey.compareTo(root.nodeKey) < 0) {
            //小于去左子树处理
            if (root.left == null) {
                root.left = nodeInserted;
                nodeInserted.parent = root;
                return true;
            } else {
                return addTreeNode(root.left, nodeInserted);
            }
        } else {
            //节点已经存在
            return false;
        }
    }

    /**
     * 将值插入对应的节点
     */
    public boolean addTreeNode(BsTreeNode<T> root, T data) {
        //插入的数值为空，直接返回插入不成功
        //这个需要使用T类型来判断是否符合类型
        if (data == null) {
            return false;
        }
        BsTreeNode<T> insertNode = new BsTreeNode<>(data);
        return addTreeNode(root, insertNode);
    }

    /**
     * 将值插入对应的节点
     */
    public boolean addTreeNode(T data) {
        if (data == null) {
            return false;
        }
        BsTreeNode<T> insertNode = new BsTreeNode<>(data);
        return addTreeNode(root, insertNode);
    }

    /**
     * 删除节点
     * 删除节点存在四种情况
     * 1、删除的节点是叶子节点
     * 2、删除的节点只有左子树节点
     * 3、删除的节点只有右子树节点
     * 4、删除的节点左右子树节点都有
     * <p>
     * 对于第一种情况，直接删除叶子节点，不涉及树结构的调整
     * 第二种情况，将其左子树替换
     * 第三种情况，将其右子树替换
     * 第四种情况，需要找到被删除节点的前置节点进行替换
     */
    public void delTreeNode(BsTreeNode<T> currentNode, T data) {
        if (data == null || currentNode == null) {
            return;
        }

        //先查找到对应节点
        if (data.compareTo(currentNode.nodeKey) > 0) {
            delTreeNode(currentNode.right, data);
        } else if (data.compareTo(currentNode.nodeKey) < 0) {
            delTreeNode(currentNode.left, data);
        } else {
            //找到需要删除的节点
            //第一种情况，叶子节点
            if (currentNode.left == null && currentNode.right == null) {
                //获取当前叶子节点的父节点
                BsTreeNode<T> parent = currentNode.parent;
                //通过父节点销毁删除的节点
                if (parent.right == currentNode) {
                    parent.right = null;
                }
                if (parent.left == currentNode) {
                    parent.left = null;
                }
            } else if (currentNode.right == null) {
                //第二种情况，只存在左子树节点
                //获取左子树节点
                BsTreeNode<T> currentNodeLeft = currentNode.left;
                currentNode.nodeKey = currentNodeLeft.nodeKey;
                //ps：无需判断当前节点的左子树节点是否存在左右子树节点，null不影响
                currentNode.left = currentNodeLeft.left;
                currentNode.right = currentNodeLeft.right;

                //修正父节点
                if (currentNodeLeft.left != null) {
                    currentNodeLeft.left.parent = currentNode;
                }
                if (currentNodeLeft.right != null) {
                    currentNodeLeft.right.parent = currentNode;
                }
            } else if (currentNode.left == null) {
                //第三种情况，只存在右子树节点，和第二种类同
                BsTreeNode<T> right = currentNode.right;
                currentNode.nodeKey = right.nodeKey;
                currentNode.left = right.left;
                currentNode.right = right.right;

                if (right.left != null) {
                    right.left.parent = currentNode;
                }
                if (right.right != null) {
                    right.right.parent = currentNode;
                }
            } else {
                //第四种情况，存在左右子树节点的情况
                //找到被删除节点的前驱节点或者后继节点，进行替换，然后再删掉前驱或者后继节点
                BsTreeNode<T> nodeRoot = currentNode.left;
                //找到前驱节点
                while (nodeRoot.right != null) {
                    nodeRoot = nodeRoot.right;
                }
                currentNode.nodeKey = nodeRoot.nodeKey;
                //再递归删除前驱节点---->叶子节点
                delTreeNode(nodeRoot, nodeRoot.nodeKey);
            }
        }
    }

    /**
     * 删除节点
     */
    public void delTreeNode(T data) {
        if (data == null || root == null) {
            return;
        }
        delTreeNode(root, data);
    }

    /**
     * 获取最小的节点
     */
    public BsTreeNode<T> findMin(BsTreeNode<T> root) {

        return root;
    }

    /**
     * 获取最大的节点
     */
    public BsTreeNode<T> findMan(BsTreeNode<T> root) {

        return root;
    }

    /**
     * 判断是否适合二叉搜索树
     */

    /**
     * 获取一个节点的前驱节点
     */

    /**
     * 获取一个节点的后继节点
     */

}
